There has been a lot of hullabaloo recently about ‘direct-product testing’ and its applications to probabilistically checkable proofs (PCPs), which are important in modern complexity theory and cryptography. This culminated in the work of Bafna, Minzer, and Vyas, who gave PCPs with great soundness and length properties (and won a best paper award at STOC last year for it).
The Bafna--Minzer--Vyas paper and its predecessors ultimately boil down to analyzing expansion properties of certain graphs, but unfortunately, even defining these graphs requires some deep number theory and algebraic group theory. (Personally, I do not understand their definition.) We revisit the direct-product testing and PCP problems using an alternative construction, called the “Kaufman--Oppenheim (KO) coset complexes, and show that the KO complexes achieve similar guarantees to the previously-studied constructions. Unlike those, the KO complexes have an elementary and strongly explicit description, and also have some nicer technical properties.
We fully define the direct-product testing problem (in the “low-soundness regime”) and the KO complex in this talk, and assume no background aside from basic probability and group theory.
Based on joint work with Ryan O'Donnell.